#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/09/23
# @Author   :Changshu
# @File     :practice_160.py
# 160. 相交链表: 编写一个程序，找到两个单链表相交的起始节点。
# 如果两个链表没有交点，返回 null.
# 在返回结果后，两个链表仍须保持原有的结构。
# 可假定整个链表结构中没有循环。
# 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

class ListNode:
	def __init__(self,x):
		self.val=x
		self.next=None
'''走两圈
def getIntersectionNode(headA:ListNode,headB:ListNode)->ListNode:
	if headA is None or headB is None:
		return None
	pA,pB=headA,headB
	while pA != pB:
		if pA is None:
			pA=headB
		else:
			pA=pA.next
		if pB is None:
			pB=headA
		else:
			pB=pB.next
	return pA
'''

'''想复杂了啊'''
def getIntersectionNode(headA:ListNode,headB:ListNode)->ListNode:
	lenA=getListNodeLength(headA)
	lenB=getListNodeLength(headB)
	if lenA==0 or lenB==0:
		return None
	pA=headA
	pB=headB
	if lenA>lenB:
		for i in range(lenA-lenB):
			pA=pA.next
	elif lenA<lenB:
		for i in range(lenB-lenA):
			pB=pB.next
	while pA is not None and pB is not None:
		if pA is pB:
			return pA
		pA = pA.next
		pB = pB.next
	return None

'''测试长度'''
def getListNodeLength(head:ListNode):
	count=0
	if head is None:
		return count
	p=head
	while p is not None:
		count+=1
		p=p.next
	return count


if __name__ == '__main__':
	headA_1=ListNode(4)
	headA_2=ListNode(1)
	headA_1.next=headA_2


	headB_1=ListNode(5)
	headB_2 = ListNode(0)
	headB_3 = ListNode(1)
	headB_1.next=headB_2
	headB_2.next=headB_3

	node1=ListNode(8)
	node2=ListNode(4)
	node3=ListNode(5)
	node1.next=node2
	node2.next=node3

	headA_2.next=node1
	headB_3.next=node1

	# print(getListNodeLength(headA_1))
	# print(getListNodeLength(headB_1))
	n=getIntersectionNode(headA_1,headB_1)
	print(n)

